# 两数之和II:  https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

class Solution:
    def twoSum(self, numbers: list, target: int) -> list:
        """ 双指针解题 """
        n = len(numbers)
        low, high = 0, n-1

        while low < high:
            if numbers[low] + numbers[high] == target:
                return [low + 1, high + 1]
            elif numbers[low] + numbers[high] < target:
                low += 1
            else:
                high -= 1
        
        return []


class Solution:
    def twoSum(self, numbers: list, target: int) -> list:
        """ 二分查找 """
        nums = numbers
        def binarySearch(nums, left, right, target):
            while left <= right:
                print(left, right)
                middle = (left + right) // 2
                if nums[middle] == target:
                    return middle
                elif nums[middle] > target:
                    right = middle - 1
                else:
                    left = middle + 1

            return -1

        n = len(nums)
        for i, num in enumerate(nums):
            t = target - num
            # 使用二分查找
            index = binarySearch(nums, i + 1, n - 1, target - num)
            if index != -1: return [i + 1, index + 1]
        return []
